package com.github.hgkmail.hello.leetcode101.pointer.graph.shortestpath;

//0 <= wi <= 100
//任意两点最短距离：floyd算法
public class LC743NetworkDelayTime {
    public int networkDelayTime(int[][] times, int n, int k) {
        if (n<=0) {
            return 0;
        }
        if (times.length<=0) {
            return -1;
        }
        //邻接矩阵
        int[][] graph=new int[n+1][n+1];
        int maxWeight=10000; //表示无穷大
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                graph[i][j]=maxWeight;
            }
        }
        for (int[] edge:times) {
            graph[edge[0]][edge[1]]=edge[2];
        }
        //floyd算法求任意2点的最短路
        for (int m = 1; m <=n; m++) { //最外层循环，插入点
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (graph[i][j] > graph[i][m] + graph[m][j]) { //若插入点之后变小，更新最短路
                        graph[i][j] = graph[i][m] + graph[m][j];
                    }
                }
            }
        }
        int maxTime=0;
        for (int i = 1; i <= n; i++) {
            if (i==k) {
                continue; //没有自环
            }
            if (graph[k][i]==maxWeight) { //存在不能达到的点
                return -1;
            }
            maxTime=Math.max(maxTime, graph[k][i]);
        }
        return maxTime;
    }

    public static void main(String[] args) {
        System.out.println(new LC743NetworkDelayTime().networkDelayTime(new int[][]{{2,1,1},{2,3,1},{3,4,1}},4,2));
    }
}
